Non-volatile memory systems, such as flash memory, have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. When writing data to a conventional flash memory system, a host typically writes data to, and reads data from, addresses within a logical address space of the memory system. The memory system then commonly maps data between the logical address space and the physical blocks or metablocks of the memory, where data is stored in fixed logical groups corresponding to ranges in the logical address space. Each fixed logical group may be stored in a separate physical block of the memory system or may be stored in runs of physical memory location in multiple physical blocks or metablocks. The memory system keeps track of how the logical address space is mapped into the physical memory but the host is unaware of this. The host keeps track of the addresses of its data files within the logical address space but the memory system generally operates without knowledge of this mapping. The mapping information is typically stored in an address table indexed such that each of the logical groups or logical address runs in the logical address space is mapped to a physical address run.
Mapping information is updated when data is modified or deleted and/or new data is written, for example. In typical memory systems, when mapping information needs to be updated, the full set of mapping entries, where the set is for a logical group, in the address table is rewritten. For example, in the scenario where the minimum size of a mapped data run is 4 KB and the memory system is fully fragmented into minimum-sized data runs, and each logical group occupies 8 MB, each logical group is mapped to 2048 unrelated physical address runs, and the set of mapping entries in the address table for a logical group occupies 16 KB. Accordingly, if the full set of mapping entries for a logical group is rewritten in the address table, up to 16 KB of space is used for the mapping entries and up to 16 KB of obsolete space is created. The obsolete space would be unusable until it is reclaimed.
Accordingly, in a memory system with high fragmentation and random 4 KB data being written, there is a unreasonable amount of overhead related to updating mapping entries in the address table and relocating data to reclaim obsolete space. The overhead incurred in such a memory system significantly affects the write performance and write amplification ratio (i.e., the ratio of the amount of data programmed, including internal copying/movement of data, relative to the amount of data written by a host) of the memory system. Lower performance and reduced device lifetime for the memory system may result.